1. Field of the Invention
The present invention relates to a technique of realizing various configurations of a CAM (Content Addressable Memory) by using a single CAM device or a plurality of CAM devices connected in a cascaded fashion.
2. Description of the Related Art
In network devices such as a switching device or a router, a CAM is widely used to achieve high operating speed and high performance.
In network devices, it is needed to deal with various data formats depending on OSI (Open System Interconnection) layers. For example, address information in layer 2 is expressed by binary data with a long bit length, and address information in layer 3 is expressed by ternary data with a short bit length. The binary data refers to data that can be in either “0” state or “1” state, and the ternary data refers to data that can be in one of states “0”, “1”, and “X” (don't care). In some cases, a combination of information in different layers is used. In this case, data has a longer bit length.
To achieve a network device used in the above-described manner, it is required to use a plurality of CAMs that are different in type (binary or ternary), bit length, and/or memory capacity, depending on data formats.
To achieve such a network device, the following techniques (1) to (3) are known.
(1) A plurality of CAM devices different in type, bit length, and/or memory capacity are used.
(2) A CAM device having a plurality of physical banks is used, and the memory configurations of the physical banks are statistically set in accordance with address information in a particular layer, as disclosed, for example, in Japanese Patent Application Publication No. 2001-236790.
(3) A plurality of data having different bit lengths are dealt with by a single CAM device or a single physical bank.
In the technique (3), for example, when 31-bit data and 62-bit data are dealt with together, a 64-bit word ternary CAM such as that shown in FIG. 8 is used.
When 31-bit data is stored in the CAM device, data is stored in both high-order 32-bit part and low-order 32-bit part of each 64-bit word. In this case, the most significant bit of each of the high-order 32-bit part and the low-order 32-bit part is used as a flag, and the remaining 31 bits are used as data bits. In this case, the flag is set to 1 to indicate that data is 31 bits in length.
In the case in which 62-bit data is stored in the CAM device, each data is divided into two pieces and respectively stored in a high-order 31-bit part and a low-order 31-bit part of one 64-bit word. In this case, 0 is stored in each flag to indicate that data is 62-bit data.
When 31-bit data is searched, searching is performed in two steps, in each of which a combination of 32-bit data consisting of 31-bit search data plus a flag bit of “1” and 32-bit X data is used. In the first step, high-order 32-bit part in the CAM is searched on the basis of 64-bit data consisting of high-order 32-bit part indicating the search data and low-order 32-bit part given as X data. In the second step, low-order 32-bit part in the CAM is searched on the basis of 64-bit data consisting of high-order 32-bit part given as X data and low-order 32-bit part given as the search data.
When 62-bit data is searched, 64-bit data consisting of 62-bit search data plus two flags both being in 0 state is used.
However, in the techniques (1) and (2), a high proportion of the storage capacity is not used depending on the configuration. In particular, when a high-capacity CAM is used, the existence of non-used portion results in a significant increase in cost. In the technique (2), only one physical bank is allowed to be assigned to only one logical bank. Besides, a technique of using a plurality of CAM devices in a cascaded fashion is not considered. In the technique (3), searching is performed in two steps and a higher-priority search result is selectively output, and thus the technique (3) needs a complicated circuit and a long processing time.